import java.util.BitSet;

/**
 * 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串（重复字符算做一个字符）。
 * <p>
 * 示例：
 * <p>
 * 输入: S = "ADOBECODEBANC", T = "ABC"
 * 输出: "BANC"
 * 说明：
 * <p>
 * 如果 S 中不存这样的子串，则返回空字符串 ""。
 * 如果 S 中存在这样的子串，我们保证它是唯一的答案。
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
        System.out.println(minWindow("a", "aa"));
    }

    /**
     * 位图算法
     *
     * @param s
     * @param t
     * @return
     */
    public static String minWindow(String s, String t) {
        BitSet sign = sign(t, 0, t.length());
        int start = 0;
        int end = s.length();
        BitSet bitSet = sign(s, start, end);
        if (match(sign, bitSet)) {
            while (true) {
                bitSet = sign(s, ++start, end);
                if (!match(sign, bitSet)) {
                    start--;
                    break;
                }
            }
            while (true) {
                bitSet = sign(s, start, --end);
                if (!match(sign, bitSet)) {
                    end++;
                    break;
                }
            }
            return s.substring(start, end);
        }
        return "";
    }

    /**
     * 位图签名
     *
     * @param s
     * @param start
     * @param end
     * @return
     */
    private static BitSet sign(String s, int start, int end) {
        BitSet bitSet = new BitSet(128);
        for (int i = start; i < end; i++) {
            bitSet.set(s.charAt(i), true);
        }
        return bitSet;
    }

    /**
     * 判断位图签名是否一致
     *
     * @param sign
     * @param bitSet
     * @return
     */
    private static boolean match(BitSet sign, BitSet bitSet) {
        BitSet newSign = (BitSet) sign.clone();
        newSign.and(bitSet);
        if (sign.equals(newSign)) {
            return true;
        }
        return false;
    }

}